﻿using System;
using System.Linq;
using Algoritmia.DataStructures.Lists;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Utils;

namespace Algoritmia.Problems.ConstrainedCoinChange
{
    public class ConstrainedCoinChanger
    {
        private readonly IList<int> _values;
        private readonly Func<IMap<Tuple<int, int>, double>> _createMap;
        private readonly IList<double> _weights;
        private readonly int _n;

        public ConstrainedCoinChanger(IList<int> values, IList<double> weights, Func<IMap<Tuple<int,int>,double>> createMap = null)
        {
            _values = values;
            _weights = weights;
            _n = values.Count;
            _createMap = createMap ?? (() => AlgoritmiaFactory.Maps<Tuple<int, int>, double>.Default);
        }

        public double Weight(int Q, IList<int> coinCounters)
        {
            if (coinCounters.Count != _n)
            {
                throw new ArgumentException("coinCounters argument must have the same number of elements as the coin system.");
            }

            var L = _createMap();
            L[new Tuple<int, int>(0, 0)] = 0;
            for(var q = 1; q <= Q; q++)
            {
                L[new Tuple<int, int>(q, 0)] = double.PositiveInfinity;
            }
            for(var n =1; n <= _n; n++ )
            {
                for(var q = 0; q <= Q; q++)
                {
                    L[new Tuple<int, int>(q, n)] =
                        Enumerable.Range(0, Math.Min(q/_values[n - 1], coinCounters[n - 1]) +1).Select(
                            i => L[new Tuple<int, int>(q - _values[n - 1]*i, n - 1)] + _weights[n - 1]*i).DefaultIfEmpty
                            (double.PositiveInfinity).Min();
                }
            }
            return L[new Tuple<int, int>(Q, _n)];
        }
    }
}
